class MinStack {
public:
    MinStack() {

    }

    void push(int val) {
        orders.push(val);
        if (mins.empty())
            mins.push(val);
        else
        {
            if (val <= mins.top())
            {
                mins.push(val);
            }
            else
            {
                int i = mins.top();
                mins.pop();
                mins.push(val);
                mins.push(i);
            }
        }
    }

    void pop() {
        int i = orders.top();
        orders.pop();
        while (!mins.empty())
        {
            int j = mins.top();
            if (i == j)
            {
                mins.pop();
                break;
            }
            else
            {
                int k = mins.top();
                mins.pop();
                spares.push(k);
            }
        }
        while (!spares.empty())
        {
            mins.push(spares.top());
            spares.pop();
        }
    }

    int top() {
        return orders.top();
    }

    int getMin() {
        return mins.top();
    }
    stack<int> orders;
    stack<int> mins;
    stack<int> spares;
};